#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    //false
    bool ans1(string s1, string s2, string s3){
        int len1 = s1.size(), len2 = s2.size(), len3 = s3.size();
        if(len1 + len2 != len3 || len3 == 0 && len1 != 0 || len3 == 0 && len2 != 0){
            return false;
        }
        if(len3 == 0 && len1 == 0 && len2 == 0){
            return true;
        }
        string cp = s3;
        int p1 = 0, p2 = 0, i = 0;
        vector<int> flag;
        while(i < len3){
            while(s1[p1] == cp[0]){
                cp.erase(0, 1);
                p1++;
                i++;
                if(cp.empty()){
                    break;
                }
            }
            flag.push_back(1);
            while(s2[p2] == cp[0]){
                cp.erase(0, 1);
                p2++;
                i++;
                if(cp.empty()){
                    break;
                }
            }
            flag.push_back(0);
            if(s1[p1] != cp[0] && s2[p1] != cp[0]){
                return false;
            }
        }
        for(int i = 0; i != flag.size()-1; i++){
            if(flag[i] == flag[i+1]){
                return false;
            }
        }
        return true;
    }

    
    bool ans2(string s1, string s2, string s3){
        int len1 = s1.size(), len2 = s2.size(), len3 = s3.size();
        if(len1 + len2 != len3){
            return false;
        }
        
        vector<vector<bool>> f(len1+1, vector<bool>(len2+1, false));
        f[0][0] = true;
        for(int i = 0; i != len1+1; i++){
            for(int j = 0; j != len2+1; j++){
                int p = i + j - 1;
                if(i > 0 && f[i-1][j] && s1[i-1] == s3[p]){
                    f[i][j] = true;
                }
                if(j > 0 && f[i][j-1] && s2[j-1] == s3[p]){
                    f[i][j] = true;
                }
            }
        }

        return f[len1][len2];
    }

};

void test1(){
    Solution s;
    string s1 = "aabcc";
    string s2 = "dbbca";
    string s3 = "aadbbcbcac";

    bool ret = s.ans2(s1, s2, s3);
    cout << ret << endl;
}

void test2(){
    Solution s;
    string s1 = "aabcc";
    string s2 = "dbbca";
    string s3 = "aadbbbaccc";

    bool ret = s.ans2(s1, s2, s3);
    cout << ret << endl;
}

void test3(){
    Solution s;
    string s1 = "aa";
    string s2 = "ab";
    string s3 = "aaba";

    bool ret = s.ans2(s1, s2, s3);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();
    test3();

    return 0;
}